/*
    Copyright 2009 Semantic Discovery, Inc. (www.semanticdiscovery.com)

    This file is part of the Semantic Discovery Toolkit.

    The Semantic Discovery Toolkit is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    The Semantic Discovery Toolkit is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with The Semantic Discovery Toolkit.  If not, see <http://www.gnu.org/licenses/>.
*/
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace SemanticDiscovery.Util {
  /**
   * General static utilities.
   * <p>
   * @author Spence Koehler
   */
  public class GeneralUtil {

    /// Utility function to combine elements from a list of collections.
    /// <p>
    /// Given a list of the form (x1 x2 x3 ... xn) where each xi has the form
    /// (y1 y2 ... ym), create a list (size m^n) of collections (each size n)
    /// that takes one yi from each xi.
    /// <p>
    /// The resulting list would be of the form (z1 z2 ... zk) where each zi
    /// has the form (yj1 yj2 ... yjn) where ji is in the range 1..m.
    /// <p>
    /// As examples:
    /// <p>  ((a b) (c d)) ==&gt; ((a c) (a d) (b c) (b d))
    /// <p>  ((a b c) (d e f)) ==&gt; ((a d) (a e) (a f) (b d) (b e) (b f) (c d) (c e) (c f))
    /// <p>  ((a b) (c d) (e f)) ==&gt; ((a c e) (a c f) (a d e) (a d f) (b c e) (b c f) (b d e) (b d f))
    /// <p>  ((a) (b) (c)) ==&gt; ((a b c))
    /// <p>  ((a)) ==&gt; ((a))
    /// <p>  ((a b c d)) ==&gt; ((a) (b) (c) (d))
    public static IList<ICollection<E>> Combine<E>(IList<ICollection<E>> collections) {
      if (collections == null) {
        return null;
      }
      IList<ICollection<E>> result = new List<ICollection<E>>();
      combineAux(collections, new List<E>(), result);
      return result;
    }

    /** Recursive auxiliary for combine(collections). */
    private static void combineAux<E>(IList<ICollection<E>> collections, 
                                      IList<E> objectAccumulator, 
                                      IList<ICollection<E>> resultList) {

      int numCollections = collections.Count;

      if (numCollections == 0) {
        return;
      }

      ICollection<E> firstCollection = collections.First();
      bool isEmpty = firstCollection == null || firstCollection.Count == 0;

      if (numCollections == 1) {
        if (!isEmpty) {
          foreach(E curObject in firstCollection) {
            IList<E> nextAccumulator = new List<E>(objectAccumulator);
            nextAccumulator.Add(curObject);
            resultList.Add(nextAccumulator);
          }
        }
        else {
          IList<E> nextAccumulator = new List<E>(objectAccumulator);
          nextAccumulator.Add(default(E));
          resultList.Add(nextAccumulator);
        }
        return;
      }

      IList<ICollection<E>> remainder = collections.Skip(1).ToList();

      if (!isEmpty) {
        foreach(E curObject in firstCollection) {
          IList<E> nextAccumulator = new List<E>(objectAccumulator);
          nextAccumulator.Add(curObject);
          combineAux(remainder, nextAccumulator, resultList);
        }
      }
      else {
        IList<E> nextAccumulator = new List<E>(objectAccumulator);
        nextAccumulator.Add(default(E));
        combineAux(remainder, nextAccumulator, resultList);
      }
    }

  }
}
